package algorithm;

/**
 * @Author wangtengyu
 * @Create 2018-03-28-9:49
 * 归并排序
 */
public class MergeSort {











    public  static void sort(int[] array,int low,int high) {
        int mid=(low+high)/2;
        if(low<high){
            sort(array,low,mid);//往下不断分解 然后合并 最后是前半段合并的
            sort(array,mid+1,high);//往下不断分解 然后合并 最后是后半段合并的
            merge(array,low,mid,high);//把前半段后半段合并
        }

    }

    private static void merge(int [] array,int low ,int mid ,int high){
        int temp[]=new int[high-low+1];
        int i=low;
        int j=mid+1;
        int k=0;
        while (i<=mid && j<=high){
            if(array[i]<array[j]){
                temp[k++]=array[i++];
            }else{
                temp[k++]=array[j++];
            }
        }
        while(i<=mid){
            temp[k++]=array[i++];
        }
        while (j<=high){
            temp[k++]=array[j++];
        }
        for(int x=0;x<temp.length;x++){
            array[low+x]=temp[x];
        }

        //写不出来的时候就想想 最后的合并情况怎么写
    }



    public static void main(String[] args) {
        int array[]={14,12,15,13,11,16};
        sort(array,0,array.length-1);
        for (int i:array){
            System.out.print(i+" ");
        }
    }




}
